{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Allocate Mailboxes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #安排邮筒"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个房屋数组<code>houses</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;，其中&nbsp;<code>houses[i]</code>&nbsp;是第 <code>i</code>&nbsp;栋房子在一条街上的位置，现需要在这条街上安排 <code>k</code>&nbsp;个邮筒。</p>\n",
    "\n",
    "<p>请你返回每栋房子与离它最近的邮筒之间的距离的 <strong>最小 </strong>总和。</p>\n",
    "\n",
    "<p>答案保证在 32 位有符号整数范围以内。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/06/13/sample_11_1816.png\" style=\"height: 154px; width: 454px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>houses = [1,4,8,10,20], k = 3\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>将邮筒分别安放在位置 3， 9 和 20 处。\n",
    "每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/06/13/sample_2_1816.png\" style=\"height: 154px; width: 433px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>houses = [2,3,5,12,18], k = 2\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>将邮筒分别安放在位置 3 和 14 处。\n",
    "每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>houses = [7,4,6,1], k = 1\n",
    "<strong>输出：</strong>8\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>houses = [3,6,14,10], k = 4\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == houses.length</code></li>\n",
    "\t<li><code>1 &lt;= n&nbsp;&lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= houses[i] &lt;= 10^4</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "\t<li>数组&nbsp;<code>houses</code>&nbsp;中的整数互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [allocate-mailboxes](https://leetcode.cn/problems/allocate-mailboxes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [allocate-mailboxes](https://leetcode.cn/problems/allocate-mailboxes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,8,10,20]\\n3', '[2,3,5,12,18]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        \n",
    "        def helper(i, j):\n",
    "            mid = (i + j) // 2\n",
    "            res = 0\n",
    "            for x in range(i, j+1):\n",
    "                res += abs(houses[x] - houses[mid])\n",
    "            return res\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, k):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return helper(idx, n - 1)\n",
    "            \n",
    "            ans = float('inf')\n",
    "            for x in range(idx, n):\n",
    "                tmp = helper(idx, x) + dfs(x+1, k-1)\n",
    "                ans = min(ans, tmp)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        h = [0 for _ in range(len(houses) + 1)]\n",
    "        for i in range(1, len(houses) + 1):\n",
    "            h[i] = houses[i - 1]\n",
    "\n",
    "        pre_sum = [0 for _ in range(len(houses) + 1)]\n",
    "        pre_sum[0] = 0\n",
    "        for i in range(1, len(houses) + 1):\n",
    "            pre_sum[i] = pre_sum[i - 1] + houses[i - 1]\n",
    "\n",
    "\n",
    "        def f(l, r):\n",
    "            if (r + l) % 2 == 0:\n",
    "                mid = int((r + l) / 2)\n",
    "            else:\n",
    "                mid = int((r + l - 1) / 2)\n",
    "            res = pre_sum[l - 1] + pre_sum[r] - 2 * pre_sum[mid]\n",
    "            if (r + l) % 2 == 0:\n",
    "                res += h[mid]\n",
    "            return res\n",
    "\n",
    "        dp = [[0 for _ in range(len(houses) + 1)] for _ in range(k + 1)]\n",
    "        houses.sort()\n",
    "        dp[1][0] = 0\n",
    "        for i in range(1, len(houses) + 1):\n",
    "            dp[1][i] = f(1, i)\n",
    "        for i in range(2, k + 1):\n",
    "            for j in range(0, len(houses) + 1):\n",
    "                dp[i][j] = math.inf\n",
    "        for i in range(2, k + 1):\n",
    "            for j in range(1, len(houses) + 1):\n",
    "                for p in range(0, j):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - 1][p] + f(p + 1, j))\n",
    "\n",
    "        return dp[k][len(houses)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        def dis(houses, i, j):\n",
    "            n = i - j\n",
    "            d = 0\n",
    "            for k in range(n//2):\n",
    "                d += houses[i-k] - houses[j+k+1]\n",
    "            return d \n",
    "        dp = [[float('inf')]*k for _ in range(len(houses))]\n",
    "        houses.sort()\n",
    "\n",
    "        for i in range(len(houses)):\n",
    "            dp[i][0] = dis(houses, i, -1)\n",
    "\n",
    "        for k_ in range(1, k):\n",
    "            for i in range(k_, len(houses)):\n",
    "                d = float('inf')\n",
    "                for j in range(i):\n",
    "                    d = min(d, dis(houses, i, j) + dp[j][k_-1])\n",
    "                dp[i][k_] = d \n",
    "        return dp[-1][k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort() #预排序处理\n",
    "        n=len(houses) #房子的总数\n",
    "        mindist=[[0 for j in range(n)] for i in range(n)]    #mindist[i][j]记录从下标为i的房子到下标为j的房子，只用一个邮筒所能达到的最小距离和\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                mid=(i+j)//2   #整除取中位数\n",
    "                for p in range(i,j+1):\n",
    "                    mindist[i][j]=mindist[i][j]+abs(houses[p]-houses[mid])\n",
    "        dp=[[float('inf') for j in range(n)] for i in range(k)]   #dp[i][j]表示i+1个邮筒，第1到第j+1个房子的最优方案对应的最小距离和\n",
    "        for j in range(n):\n",
    "            dp[0][j]=mindist[0][j]\n",
    "        for i in range(1,k):\n",
    "            for j in range(n):\n",
    "                for p in range(i-1,j):\n",
    "                    dp[i][j]=min(dp[i][j],dp[i-1][p]+mindist[p+1][j])\n",
    "        return dp[k-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        if k>= len(houses): return 0\n",
    "        houses.sort()\n",
    "\n",
    "        def getdistance(n,start):\n",
    "            if n==1: return 0\n",
    "            elif n==2: return abs(houses[start]-houses[start+1])\n",
    "            else:\n",
    "                times=n//2\n",
    "                ans=0\n",
    "                for i in range(times):\n",
    "                    ans+=abs(houses[start+i]-houses[start+n-1-i])\n",
    "                return ans\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dp(h,k,start):\n",
    "            if h<=k: return 0\n",
    "            if k==1: return getdistance(h,start)\n",
    "            ans=float(\"inf\")\n",
    "            for i in range(1,h-k+2):\n",
    "                ans=min(ans,getdistance(i,start)+dp(h-i,k-1,start+i))\n",
    "            return ans\n",
    "\n",
    "        return dp(len(houses),k,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        n = len(houses)\n",
    "        houses.sort()\n",
    "        f = [[inf] * n for _ in range(k)]\n",
    "        def dst(l, r):\n",
    "            res = 0\n",
    "            while l < r:\n",
    "                res += abs(houses[l] - houses[r])\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return res\n",
    "        for i in  range(n):\n",
    "            f[0][i] = dst(0, i)\n",
    "        for i in range(1, k):\n",
    "            for j in range(i, n - (k-i-1)):\n",
    "                for m in range(i-1, j):\n",
    "                    f[i][j] = min(f[i][j], f[i-1][m] + dst(m+1, j))\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "        for l in range(n - 2, -1, -1):\n",
    "            for r in range(l + 1, n):\n",
    "                cost[l][r] = cost[l + 1][r - 1] + houses[r] - houses[l]\n",
    "        f = [[inf] * (k + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            # 前i个房子一个邮箱的情况\n",
    "            f[i][1] = cost[0][i]\n",
    "            # 枚举邮箱个数\n",
    "            for j in range(2, min(k, i + 1) + 1):\n",
    "                # 枚举上一个邮箱的所管辖的位置的右端点\n",
    "                for i0 in range(i):\n",
    "                    if f[i0][j - 1] != inf:\n",
    "                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost[i0 + 1][i])\n",
    "        return f[n - 1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "        for l in range(n - 2, -1, -1):\n",
    "            for r in range(l + 1, n):\n",
    "                cost[l][r] = cost[l + 1][r - 1] + houses[r] - houses[l]\n",
    "        f = [[inf] * (k + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            f[i][1] = cost[0][i]\n",
    "            for j in range(2, min(k, i + 1) + 1):\n",
    "                for i0 in range(i):\n",
    "                    if f[i0][j - 1] != inf:\n",
    "                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost[i0 + 1][i])\n",
    "        return f[n - 1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        inf = 10**9\n",
    "        n = len(houses)\n",
    "        houses.sort()\n",
    "        dp = [[inf for _ in range(k+1)] for _ in range(n+1)]\n",
    "        for i in range(0, k+1):\n",
    "            dp[i][i] = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, min(k+1, i+1)):\n",
    "                for x in range(j-1, i):\n",
    "                    cost = 0\n",
    "                    l = x+1\n",
    "                    r = i\n",
    "                    while l <= r:\n",
    "                        # print(i, j, l, r, houses)\n",
    "                        cost += houses[r-1] - houses[l-1]\n",
    "                        l += 1\n",
    "                        r -= 1\n",
    "                    dp[i][j] = min(dp[i][j], dp[x][j-1] + cost)\n",
    "                    # print(i,j, dp[i][j], x, j-1, cost)\n",
    "        # print(dp)\n",
    "        return dp[n][k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, nums: List[int], K: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                cost[i][j] = cost[i + 1][j - 1] + nums[j] - nums[i]\n",
    "        f = [[inf] * (K + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            f[i][1] = cost[0][i]\n",
    "            for j in range(2, min(i + 1, K) + 1):\n",
    "                for u in range(i):\n",
    "                    f[i][j] = min(f[i][j], f[u][j - 1] + cost[u + 1][i])\n",
    "        return f[n - 1][K]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        n = len(houses)\n",
    "\n",
    "        houses.sort()\n",
    "\n",
    "        @cache\n",
    "        def dp(idx, t):\n",
    "            if t == 0 and idx == n:\n",
    "                return 0\n",
    "            elif t == 0:\n",
    "                return inf\n",
    "            elif idx == n:\n",
    "                return inf\n",
    "\n",
    "            ret = inf\n",
    "\n",
    "            for i in range(idx + 1, n + 2 - t):\n",
    "                d = sum(abs(houses[j] - houses[(i + idx) // 2]) for j in range(idx, i))\n",
    "\n",
    "                ret = min(ret, d + dp(i, t - 1))\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()#排序\n",
    "        pre = [0]#前缀和\n",
    "        l = len(houses)\n",
    "        for i in range(l):\n",
    "            pre.append(pre[-1] + houses[i])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, k):#分别是房屋下标和剩余邮筒数量\n",
    "            if l - i <= k:#如果邮筒数量大于等于房子数量，那么距离和一定为0\n",
    "                return 0\n",
    "            elif k == 1:#如果邮筒数量为1\n",
    "                j = (l + i) // 2#中位数\n",
    "                return houses[j] * (j - i) - (pre[j] - pre[i]) + pre[l] - pre[j] - houses[j] * (l - j)#中位数 * 左区间大小 - 左区间和 + 右区间和 - 中位数 * 右区间大小\n",
    "            res = dfs(i + 1, k - 1)#当前邮筒只覆盖一个房子\n",
    "            for n in range(i + 1, l):#覆盖多个房子\n",
    "                j = (n + 1 + i) // 2#中位数\n",
    "                res = min(res, houses[j] * (j - i) - (pre[j] - pre[i]) + pre[n + 1] - pre[j] - houses[j] * (n + 1 - j) + dfs(n + 1, k - 1))#中位数 * 左区间大小 - 左区间和 + 右区间和 - 中位数 * 右区间大小 + 继续深搜的结果\n",
    "            return res\n",
    "        return dfs(0, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def minDistance(self, houses: List[int], k: int) -> int:\n",
    "       houses.sort()\n",
    "       n = len(houses)\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == n :\n",
    "             return 0\n",
    "          if j == k :\n",
    "             return inf\n",
    "          res = inf\n",
    "          for x in range(i, n) :\n",
    "             res = min(res, dfs(x + 1, j + 1) + dis(i, x))\n",
    "          return res\n",
    "       def dis(i: int , j: int) -> int:\n",
    "          res = 0\n",
    "          while i < j:\n",
    "            res += houses[j] - houses[i]\n",
    "            j -= 1\n",
    "            i += 1\n",
    "          return res\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int: \n",
    "        Len = len(houses)\n",
    "        houses.sort()\n",
    "        @cache \n",
    "        def get_dis(i, j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            elif j == i+1:\n",
    "                return houses[j-1] - houses[i-1]\n",
    "            else:\n",
    "                return get_dis(i+1, j-1) + houses[j-1] - houses[i-1]\n",
    "\n",
    "\n",
    "\n",
    "        @cache \n",
    "        def f(n, k): # 前n个房子， k 个邮箱\n",
    "            if k == 1:\n",
    "                return get_dis(1, n)\n",
    "            t = inf \n",
    "            for i in range(k-1, n):\n",
    "                t = min(t, f(i, k-1) + get_dis(i+1, n))\n",
    "            return t \n",
    "        return f(Len, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        def dis(l, r):\n",
    "            mid = (l + r) >> 1\n",
    "            return sum(houses[mid + 1: r + 1]) - sum(houses[l:mid + 1]) + houses[mid] * abs((mid - l + 1) - (r - mid))\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == len(houses):\n",
    "                return 0 if j == 0 else inf\n",
    "            return min(dfs(t + 1, j - 1) + dis(i, t) for t in range(i, len(houses)))\n",
    "\n",
    "        houses.sort()\n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        # 预处理，获得[i,j]区域内放置一个桶的最小距离,将一个桶放置到屋子中位时距离将最小\n",
    "        cost = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                # 遍历[i,j]的房子，房子位置-[i,j]中位距离和为[i,j]放置一个桶的最小距离\n",
    "                for curK in range(i, j+1):\n",
    "                    cost[i][j] += abs(houses[curK] - houses[(i+j)//2])\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, curK):\n",
    "            if i == n: # 遍历到末尾，没有值\n",
    "                return float(\"inf\")\n",
    "            if curK == 1: # 只剩下一个桶，直接安放\n",
    "                return cost[i][n-1]\n",
    "            ans = float(\"inf\")\n",
    "            for j in range(i, n):\n",
    "                ans = min(ans, cost[i][j] + dfs(j+1, curK-1))\n",
    "            return ans\n",
    "        return dfs(0, k)\n",
    "    def minDistance2(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        right = max(houses)\n",
    "        def getCost(stationNums):\n",
    "            cost = 0\n",
    "            ns = len(stationNums)\n",
    "            for h in houses:\n",
    "                postIdx = bisect.bisect_left(stationNums, h)\n",
    "                if postIdx == 0:\n",
    "                    cost += abs(stationNums[0] - h)\n",
    "                elif postIdx == ns:\n",
    "                    cost += abs(stationNums[-1] - h)\n",
    "                else:\n",
    "                    cost += min(abs(stationNums[postIdx-1] - h), abs(stationNums[postIdx] - h))\n",
    "            return cost\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, curK, stationNums):\n",
    "            if curK == 0:\n",
    "                return getCost(stationNums)\n",
    "            ans = float(\"inf\")\n",
    "            for postStation in range(i, right+1):\n",
    "                ans = min(ans, dfs(postStation, curK - 1, stationNums + tuple([postStation])))\n",
    "            return ans\n",
    "        return dfs(0, k, tuple([]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        @cache\n",
    "        def f(i,j,box_nums):\n",
    "            if box_nums>=j-i:return 0\n",
    "            if box_nums==1:\n",
    "                # if (j-i)%2==1: \n",
    "                mid=houses[(i+j)//2]\n",
    "                # else :mid=houses[(i+j)//2]\n",
    "                dis=sum(\n",
    "                    [abs(mid-houses[k]) for k in range(i,j,1)]\n",
    "                )\n",
    "                return dis\n",
    "            else:\n",
    "                ret=min(\n",
    "                    [f(i,k,box_nums-1)+f(k,j,1) for k in range(i+1,j,1)]\n",
    "                )\n",
    "                return ret\n",
    "        return f(0,len(houses),k)\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minDistance(self, h: List[int], k: int) -> int:\n",
    "#         h.sort()\n",
    "#         @cache \n",
    "#         def f(i,j,k): #houses[i,j)之间安排k个邮筒\n",
    "#             if j - i <= k:  return 0\n",
    "#             if k == 1 : return h[j-1]-h[i] + f(i+1,j-1,k)\n",
    "#             return min(\n",
    "#                 f(i,m,k-1) + f(m,j,1) for m in range(i+k-1,j)\n",
    "#             )\n",
    "#         return f(0,len(h),k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        n = len(houses)\n",
    "        houses.sort()\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "        \n",
    "        @cache\n",
    "        def cal(i, j):\n",
    "            if i >= j: return 0\n",
    "            cost[i][j] = cal(i + 1, j - 1) + houses[j] - houses[i]\n",
    "            return cost[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                cal(i, j)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j == 1: return cost[0][i]\n",
    "            res = inf\n",
    "            for i0 in range(j - 2, i):\n",
    "                if j >= 2: res = min(res, dfs(i0, j - 1) + cost[i0 + 1][i])\n",
    "            return res\n",
    "        return dfs(n - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        # houses[i:j]放置k个邮筒\n",
    "        @cache\n",
    "        def f(i, j, k):\n",
    "            if j-i+1 < k:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return houses[j]-houses[i]+f(i+1, j-1, 1)\n",
    "            return min(f(i, mid, k-1)+f(mid+1, j, 1) for mid in range(i, j))\n",
    "        return f(0, n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, h: List[int], k: int) -> int:\n",
    "        h.sort()\n",
    "        n = len(h)\n",
    "        @cache\n",
    "        def f(i, j, k):\n",
    "            if i==j:\n",
    "                if k>=0:\n",
    "                    return 0 \n",
    "                return float('inf')\n",
    "            else:\n",
    "                if k==1:\n",
    "                    d = (j-i)//2 \n",
    "                    tmp = (h[i+d] + h[j-d])/2 \n",
    "                    ans = 0 \n",
    "                    for ix in range(i, j+1):\n",
    "                        ans += abs(tmp - h[ix])\n",
    "                    return  ans \n",
    "                else:\n",
    "                    ans = float('inf')\n",
    "                    for ix in range(i+1, j+1):\n",
    "                        ans = min(ans, f(i, ix-1, k-1) + f(ix, j, 1))\n",
    "                    return ans \n",
    "        return int(f(0, n-1, k))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], K: int) -> int:\n",
    "        n = len(houses)\n",
    "        houses.sort()\n",
    "        @cache\n",
    "        def dfs(l,r,k):\n",
    "            if l>=r:\n",
    "                return 0\n",
    "\n",
    "            if k == 1:\n",
    "                return houses[r] - houses[l] + dfs(l+1,r-1,1)\n",
    "\n",
    "            ans = inf\n",
    "            for j in range(l,r):\n",
    "                ans = min(ans, dfs(l,j,1)+dfs(j+1,r,k-1))\n",
    "            return ans\n",
    "        return dfs(0,n-1,K)\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        \n",
    "        n = len(houses)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j,k):\n",
    "            if i >= j:return 0\n",
    "            if k == 1:\n",
    "                return houses[j] - houses[i] + dfs(i+1,j-1,1)\n",
    "            ans = inf\n",
    "            for l in range(i,j+1):\n",
    "                ans = min(ans,dfs(i,l,1) + dfs(l+1,j,k-1))\n",
    "            return ans\n",
    "        houses.sort()\n",
    "        return dfs(0,len(houses)-1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        n = len(houses)\n",
    "        houses.sort()\n",
    "\n",
    "        # when house i to house j share one mailbox, the optimal allocation is the median house position.\n",
    "        @lru_cache(n * (n + 1) // 2)\n",
    "        def one_mailbox_min_dist(i: int, j: int) -> int:\n",
    "            ret = 0\n",
    "            while i < j:\n",
    "                ret += houses[j] - houses[i]\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return ret\n",
    "\n",
    "        # minimum distance for first i + 1 houses with j + 1 mailboxes\n",
    "        @lru_cache(n * k)\n",
    "        def min_dist(i: int, j: int) -> int:\n",
    "            if j == 0:\n",
    "                return one_mailbox_min_dist(0, i)\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            # last one mailbox for i - r houses\n",
    "            return min(min_dist(r, j - 1) + one_mailbox_min_dist(r + 1, i) for r in range(i))\n",
    "\n",
    "        return min_dist(n - 1, k - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import gc; gc.disable()\n",
    "ndp = [0]*101\n",
    "dp = [0]*101\n",
    "class Solution:\n",
    "    def minDistance(self, A: List[int], k: int) -> int:\n",
    "        n = len(A)\n",
    "        A.sort()\n",
    "        pre = list(accumulate(A, initial=0))\n",
    "        @cache\n",
    "        def onegroup(l, r):\n",
    "            m1 = (r+l-1)//2\n",
    "            m2 = (r+l)//2\n",
    "            return pre[r] - pre[m2] - pre[m1+1] + pre[l]\n",
    "        \n",
    "        # vk = 1\n",
    "        for sz in range(0, n+1): dp[sz] = onegroup(0, sz)\n",
    "        \n",
    "        def dc(sz_l, sz_r, p_l, p_r):\n",
    "            \"\"\" both closed interval \"\"\"\n",
    "            if sz_l > sz_r: return\n",
    "            sz_m = (sz_l+sz_r+1)//2\n",
    "            p, p_cost = p_l, dp[p_l] + onegroup(p_l, sz_m)\n",
    "            for can_p in range(p_l+1, p_r+1):\n",
    "                if (can_p_cost := dp[can_p] + onegroup(can_p, sz_m)) < p_cost: \n",
    "                    p, p_cost = can_p, can_p_cost\n",
    "\n",
    "            ndp[sz_m] = p_cost\n",
    "            dc(sz_l, sz_m-1, p_l, p)\n",
    "            dc(sz_m+1, sz_r, p, p_r)\n",
    "        \n",
    "        for vk in range(2, k+1):\n",
    "            dc(vk, n, 0, n)\n",
    "            for i in range(0, n+1): dp[i] = ndp[i]\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        dist = [[[0 for i in range(k + 1)] for i in range(len(houses))] for i in range(len(houses))]\n",
    "        for i in range(len(houses)):\n",
    "            for j in range(i, len(houses)):\n",
    "                if i == j:\n",
    "                    dist[i][j][1] = 0\n",
    "                elif i == j - 1:\n",
    "                    dist[i][j][1] = houses[j] - houses[i]\n",
    "                else:\n",
    "                    dist[i][j][1] = self.calculate_distance(houses[i:j+1], houses[i + (j - i) // 2])\n",
    "        for kk in range(2, k):\n",
    "            for i in range(len(houses)):\n",
    "                for j in range(i + kk - 1, len(houses)):\n",
    "                    min_dist = -1\n",
    "                    for pivot in range(i + kk - 1, j + 1):\n",
    "                        if min_dist == -1 or min_dist > dist[i][pivot - 1][kk-1] + dist[pivot][j][1]:\n",
    "                            min_dist = dist[i][pivot - 1][kk-1] + dist[pivot][j][1]\n",
    "                    dist[i][j][kk] = min_dist\n",
    "        if k > 1:\n",
    "            min_dist = -1\n",
    "            for pivot in range(k - 1, len(houses)):\n",
    "                if min_dist == -1 or min_dist > dist[0][pivot - 1][k-1] + dist[pivot][len(houses) - 1][1]:\n",
    "                    min_dist = dist[0][pivot - 1][k-1] + dist[pivot][len(houses) - 1][1]\n",
    "            dist[0][len(houses) - 1][k] = min_dist\n",
    "        return dist[0][len(houses) - 1][k]\n",
    "\n",
    "    def calculate_distance(self, houses: List[int], post_box : int) -> int:\n",
    "        dist = 0\n",
    "        for house in houses:\n",
    "            dist += abs(house - post_box)\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        dp = [[[0 for i in range(len(houses))] for j in range(len(houses))] for t in range(k)]\n",
    "        for number1 in range(k):\n",
    "            if number1 == 0:\n",
    "                for i in range(len(houses)):\n",
    "                    for j in range(i,len(houses)):\n",
    "                        if i == j:\n",
    "                            dp[number1][i][j] = 0\n",
    "                        else:\n",
    "                            size1 = i\n",
    "                            size2 = j\n",
    "                            while size2 > size1:\n",
    "                                dp[number1][i][j] += houses[size2] - houses[size1]\n",
    "                                size1 += 1\n",
    "                                size2 -= 1\n",
    "            else:\n",
    "                rig = len(houses)-(k-number1-1)\n",
    "                for  rig1 in range(number1,rig):\n",
    "                    for i in range(rig1-number1+1):\n",
    "                        if dp[number1][0][rig1] == 0:\n",
    "                            dp[number1][0][rig1] = dp[number1-1][0][rig1-i-1] + dp[0][rig1-i][rig1]\n",
    "                        else:\n",
    "                            dp[number1][0][rig1] = min(dp[number1-1][0][rig1-i-1] + dp[0][rig1-i][rig1],dp[number1][0][rig1])\n",
    "        return dp[-1][0][len(houses)-1]\n",
    "                \n",
    "\n",
    "                                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int: \n",
    "        if len(houses)<=k:\n",
    "            return 0 \n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        inf = 100*10000+1\n",
    "        # 3-dim dp:\n",
    "        # 100 x 100 x 100\n",
    "        # 在前 i 个房子中，放置了 j 个邮筒， 最后一个邮筒的位置是第 l 个房子\n",
    "        answer = [[[inf]*n for _ in range(k)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(k):\n",
    "                for l in range(j,i+1): \n",
    "                    if j>=i and l==i:\n",
    "                        answer[i][j][l] = 0\n",
    "                        continue\n",
    "                    if j==0:\n",
    "                        # 只有一个邮筒，它放在了第l个房子的位置 \n",
    "                        answer[i][j][l] = sum([abs(x-houses[l])for x in houses[:i+1]] )\n",
    "                    elif l<i:\n",
    "                        # 最后一个邮筒，并不放在最后一个房子的位置\n",
    "                        answer[i][j][l] = answer[l][j][l] + sum([abs(x-houses[l])for x in houses[l+1:i+1]] )\n",
    "                    else:\n",
    "                        # 有多个邮筒，它们放在不同的位置\n",
    "                        # 开始检索倒数第二个邮筒所有可能的位置\n",
    "                        tt = inf\n",
    "                        for ll in reversed(range(j-1,l)): \n",
    "                            t = answer[ll][j-1][ll] + sum([min(abs(x-houses[ll]),abs(x-houses[l]))for x in houses[ll+1:i+1]] )\n",
    "                            tt = min(t,tt)\n",
    "                        answer[i][j][l] = tt\n",
    "        xx = answer[n-1][k-1]\n",
    "        return min(xx)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        if len(houses) <= k:\n",
    "            return 0 \n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        # 3-dim dp:\n",
    "        # 100 x 100 x 100\n",
    "        # 在前 i 个房子中，放置了 j 个邮筒， 最后一个邮筒的位置是第 l 个房子\n",
    "        dp = [[[float('+inf')] * n for _ in range(k)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(k):\n",
    "                for l in range(j,i+1): \n",
    "                    if j >= i and l == i:\n",
    "                        dp[i][j][l] = 0\n",
    "                        continue\n",
    "                    if j == 0:\n",
    "                        # 只有一个邮筒，它放在了第l个房子的位置 \n",
    "                        dp[i][j][l] = sum([abs(x-houses[l])for x in houses[:i+1]] )\n",
    "                    elif l < i:\n",
    "                        # 最后一个邮筒，并不放在最后一个房子的位置\n",
    "                        dp[i][j][l] = dp[l][j][l] + sum([abs(x-houses[l])for x in houses[l+1:i+1]] )\n",
    "                    else:\n",
    "                        # 有多个邮筒，它们放在不同的位置\n",
    "                        # 开始检索倒数第二个邮筒所有可能的位置\n",
    "                        tt = inf\n",
    "                        for ll in reversed(range(j-1, l)): \n",
    "                            t = dp[ll][j-1][ll] + sum([min(abs(x-houses[ll]),abs(x-houses[l]))for x in houses[ll+1:i+1]] )\n",
    "                            tt = min(t,tt)\n",
    "                        dp[i][j][l] = tt\n",
    "        return min(dp[n-1][k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        dp = [[[0] * (k + 1) for _ in range(len(houses))] for i in range(len(houses))]\n",
    "        for i in range(len(houses)):\n",
    "            dp[i][i][1] = 0\n",
    "            x = 0\n",
    "            for j in range(i + 1, len(houses)):\n",
    "                if (j - i) % 2 == 1:\n",
    "                    x += houses[j] - houses[j - 1]\n",
    "                    dp[i][j][1] = x + dp[i][j - 1][1]\n",
    "                else:\n",
    "                    x += houses[j] - houses[j - 1]\n",
    "                    x -= houses[i + (j - i) // 2] - houses[i + (j - i) // 2 - 1]\n",
    "                    dp[i][j][1] = x + dp[i][j - 1][1]\n",
    "        for i in range(2, k + 1):\n",
    "            for j in range(len(houses)):\n",
    "                for l in range(j + 1, len(houses)):\n",
    "                    dp[j][l][i] = min([dp[j][m][i - 1] + dp[m + 1][l][1] for m in range(j, l)])\n",
    "        return dp[0][len(houses) - 1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "\n",
    "        # 前ii个位置放kk个油桶的最小距离和, 状态转移时候考虑房子的分组，同一组对应的邮箱就放在中位数位置\n",
    "        # min_dis表示ii+1位置的房子到其分组的中位数位置的距离\n",
    "        @lru_cache(typed=False, maxsize=12800000000)\n",
    "        def dp(ii, kk, min_dis):\n",
    "            if kk == 1:\n",
    "                start = 0\n",
    "                mid = (start + ii) // 2\n",
    "                if min_dis is not None and houses[ii+1] - houses[mid] < min_dis:\n",
    "                    return 0x7fffffff\n",
    "                else:\n",
    "                    sum = 0\n",
    "                    for i in range(start, ii+1):\n",
    "                        sum += abs(houses[i] - houses[mid])\n",
    "                    return sum\n",
    "            else:\n",
    "                ans = 0x7fffffff\n",
    "                for start in range(ii, kk-2, -1):\n",
    "                    mid = (start + ii) // 2\n",
    "                    if min_dis is not None and houses[ii+1] - houses[mid] < min_dis:\n",
    "                        continue\n",
    "\n",
    "                    sum = 0\n",
    "                    for i in range(start, ii+1):\n",
    "                        sum += abs(houses[i] - houses[mid])\n",
    "                    \n",
    "                    ret = dp(start-1, kk-1, houses[mid] - houses[start])\n",
    "                    if ret != 0x7fffffff:\n",
    "                        ans = min(ans, ret + sum)\n",
    "                return ans\n",
    "\n",
    "        return dp(len(houses)-1, k, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], kk: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses) \n",
    "        f = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "\n",
    "        for lenn in range(2, n + 1): \n",
    "            for i in range(n + 1 - lenn): \n",
    "                j = i + lenn - 1 \n",
    "                for k in range(kk + 1): \n",
    "                    if k > lenn: continue\n",
    "                    if k == 1: f[i][j][k] = houses[j] - houses[i] + f[i + 1][j - 1][k]\n",
    "                    else: \n",
    "                        f[i][j][k] = inf\n",
    "                        for t in range(i + k - 1, j + 1): \n",
    "                            f[i][j][k] = min(f[i][j][k], f[i][t - 1][k - 1] + f[t][j][1])\n",
    "        \n",
    "        return f[0][n - 1][kk]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        length = len(houses)\n",
    "        houses.sort()\n",
    "        if length <= k:\n",
    "            return 0\n",
    "\n",
    "        def find_min_distance(points:List[int]):\n",
    "            mid = math.floor(len(points)/2)        \n",
    "            return sum([abs(p-points[mid]) for p in points])\n",
    "\n",
    "        dp = np.zeros((length,k))\n",
    "        for i in range(length):\n",
    "            dp[i][0] = find_min_distance(houses[:i+1])\n",
    "\n",
    "       \n",
    "        for loop in range(1,k):\n",
    "            for i in range(length):\n",
    "                if i <= loop:\n",
    "                    dp[i][loop] = 0\n",
    "                else:\n",
    "                    dp[i][loop] = 0\n",
    "                    prev_loop  = loop -1\n",
    "                    temp = []\n",
    "                    for j in range(prev_loop,i):\n",
    "                        temp.append(dp[j][prev_loop]+find_min_distance(houses[j+1:i+1]))\n",
    "                    dp[i][loop] = min(temp)\n",
    "        return int(dp[length-1][k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        dp = [[[inf] * n for _ in range(n)] for _ in range(k)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                l = j - i + 1\n",
    "                if l % 2:\n",
    "                    point = houses[i + l//2]\n",
    "                else:\n",
    "                    point = (houses[i + l//2 - 1] + houses[i + l//2]) // 2\n",
    "                dp[0][i][j] = sum(abs(p - point) for p in houses[i:j+1])\n",
    "            dp[0][i][i] = 0\n",
    "        for m in range(1, k):\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    dp[m][i][j] = min(dp[0][i][k] + dp[m-1][k+1][j] for k in range(i, j))\n",
    "        return dp[k-1][0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        num = len(houses)\n",
    "        # w[i, j] 为从i+1个开始，到j个house的放1个邮筒的最小值\n",
    "        import numpy as np\n",
    "        w = np.zeros((num, num))\n",
    "        dp = np.zeros((num, k))\n",
    "        # dp[i, j] 为到第i个house放j个邮筒的最小值\n",
    "        from collections import defaultdict\n",
    "        result = defaultdict(list)\n",
    "\n",
    "        for i in range(num):\n",
    "            for j in range(i + 1, num):\n",
    "                w[i, j] = w[i, j - 1] + houses[j] - houses[(j + i) // 2]\n",
    "        # 初始化边界值\n",
    "        for ss in range(num):\n",
    "            if ss < k:\n",
    "                dp[ss, ss] = 0\n",
    "            dp[ss, 0] = w[0, ss]\n",
    "        # 两个状态转移方程\n",
    "        # w[l, r] = w[l +1, r - 1] + h[r] - h[l] = w[l, r -1 ] + h[r] - h[(r + l) /2]\n",
    "        # f[i][j] = min(f[i0][j -1 ] + w(i0, i))\n",
    "        for ii in range(0, num):\n",
    "            if ii < 1:\n",
    "                continue\n",
    "            for jj in range(1, k):\n",
    "                if jj >= ii:\n",
    "                    continue\n",
    "                dp[ii, jj] = 999999999\n",
    "                for kk in range(jj - 1, ii):\n",
    "                    dp[ii, jj] = min(dp[ii, jj], dp[kk][jj - 1] + w[kk + 1, ii])\n",
    "        # print(dp[num - 1, k - 1])\n",
    "        return int(dp[num - 1, k - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        num = len(houses)\n",
    "        # w[i, j] 为从i+1个开始，到j个house的放1个邮筒的最小值\n",
    "        import numpy as np\n",
    "        w = np.zeros((num, num))\n",
    "        dp = np.zeros((num, k))\n",
    "        # dp[i, j] 为到第i个house放j个邮筒的最小值\n",
    "        # from collections import defaultdict\n",
    "        # result = defaultdict(list)\n",
    "\n",
    "        for i in range(num):\n",
    "            for j in range(i + 1, num):\n",
    "                w[i, j] = w[i, j - 1] + houses[j] - houses[(j + i) // 2]\n",
    "\n",
    "        # 两个状态转移方程\n",
    "        # w[l, r] = w[l +1, r - 1] + h[r] - h[l] = w[l, r -1 ] + h[r] - h[(r + l) /2]\n",
    "        # f[i][j] = min(f[i0][j -1 ] + w(i0, i))\n",
    "        for ii in range(0, num):\n",
    "            dp[ii, 0] = w[0, ii]\n",
    "            if ii < 1:\n",
    "                continue\n",
    "            for jj in range(1, min(k, num)):\n",
    "                if jj >= ii:\n",
    "                    continue\n",
    "                dp[ii, jj] = 999999\n",
    "                for kk in range(jj - 1, ii):\n",
    "                    dp[ii, jj] = min(dp[ii, jj], dp[kk][jj - 1] + w[kk + 1, ii])\n",
    "        return int(dp[num - 1, k - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        import numpy as np\n",
    "        houses.sort()\n",
    "\n",
    "        n = len(houses)\n",
    "        partition_res = np.zeros((n, n))\n",
    "        for i in range(n):\n",
    "            partition_res[i, i] = 0\n",
    "            for j in range(i):\n",
    "                partition_res[j, i] = houses[i] - houses[j]\n",
    "                if j <= i - 2:\n",
    "                    partition_res[j, i] += partition_res[j + 1, i - 1]\n",
    "\n",
    "        states = np.full((len(houses) + 1, k + 1), -1)\n",
    "        states[0, 0] = 0\n",
    "\n",
    "        for i in range(1, len(houses) + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                for m in range(1, i + 1):\n",
    "                    if states[m - 1, j - 1] >= 0:\n",
    "                        nv = states[m - 1, j - 1] + partition_res[m - 1, i - 1]\n",
    "                        if states[i, j] < 0 or nv < states[i, j]:\n",
    "                            states[i, j] = nv\n",
    "\n",
    "        return int(states[n, k])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
